/*
 * @lc app=leetcode.cn id=1049 lang=golang
 *
 * [1049] 最后一块石头的重量 II
 */

// @lc code=start
func lastStoneWeightII(stones []int) int {
	sum := 0
	for _, v := range stones {
		sum += v
	}
	// 背包大小
	bg := sum / 2
	// 动规数组
	n := len(stones)
	dp := make([][]int, n+1)
	for i, _ := range dp {
		dp[i] = make([]int, bg+1)
	}
	// for i,_:=range dp[0]{

	// }
	// dp[i][j] i 个石头能在表示 j 下最大的重量
	for i := 1; i <= n; i++ {
		for j := 1; j <= bg; j++ {
			if j < stones[i-1] {
				dp[i][j] = dp[i-1][j]
			} else {
				// 分为使用该石头与不使用该石头
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i-1]]+stones[i-1])
			}
		}
	}
	// fmt.Println(dp)
	return sum - dp[n][bg] - dp[n][bg]
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

// @lc code=end

